package com.cheung.leetcode.arr;

import java.util.HashMap;
import java.util.Map;

public class LC76 {

    public static String minWindow(String s, String t) {
        int min = Integer.MAX_VALUE;
        if (s.length() < t.length()) {
            return "";
        }


        Map<Character, Integer> th = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            th.put(t.charAt(i), th.getOrDefault(t.charAt(i), 0) + 1);
        }

        Map<Character, Integer> sh = new HashMap<>();

        int left = 0;
        int start = 0;

        for (int right = 0; right < s.length(); right++) {
            sh.put(s.charAt(right), sh.getOrDefault(s.charAt(right), 0) + 1);
            while (check(sh, th)) {
                // 将最小的结果保存起来
                if (right - left + 1 < min) {
                    min = right - left + 1;
                    start = left;
                }

                // 左边
                char key = s.charAt(left);
                sh.put(key, sh.get(key) - 1);
                if (sh.get(key) == 0) {
                    sh.remove(key);
                }
                left++;
            }

        }
        return min == Integer.MAX_VALUE ? "" : s.substring(start, start + min);
    }

    public static boolean check(Map<Character, Integer> hash1, Map<Character, Integer> hash2) {

        // str1是否覆盖str2,则必须str1的key包含str2的key,并且每个key的值大于等于
        boolean b = hash1.keySet().containsAll(hash2.keySet());
        if (b) {
            for (Character c : hash2.keySet()) {
                b &= hash1.get(c).compareTo(hash2.get(c)) >= 0;
            }
        }

        return b;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(minWindow(s, t));
    }
}
